//静态链表（静态顺序链表）
#ifndef __STATICLIST__HPP
#define __STATICLIST__HPP

#include"VirtualLinkedList.hpp"

namespace NgSiuKei {

template<class TheClass>
class StaticList: public VirtualLinkedList<TheClass> {
    public:
    StaticList(void);
    ~StaticList(void);

    public:
    //清空
    void clear(void);
    //获取特定下标的元素值
    TheClass getVal(const U_L_L &index) const;
    //查找数据，返回下标，表没有则抛出异常：EXCEPTION_CAN_NOT_FIND
    U_L_L findVal(const TheClass &val) const;
    //插入数据
    void insertVal(const TheClass &val, const U_L_L &index);
    //删除特定下标的元素，返回元素值
    TheClass deleteWithIndex(const U_L_L &index);
    //打印表
    void print(void);

    private:
    P_TC_I *p;
};

template<class TheClass>
StaticList<TheClass>::StaticList(void): VirtualLinkedList<TheClass>() {
    this->p = new P_TC_I[MAX_SIZE];
    this->clear();
}

template<class TheClass>
StaticList<TheClass>::~StaticList(void) {
    if(nullptr != this->p) {
        delete this->p;
        this->p = nullptr;
    }
}

template<class TheClass>
void StaticList<TheClass>::clear(void) {
    this->size = 0;
    if(nullptr != this->p) {
        for(U_L_L i=0; i<MAX_SIZE-1; ++i) {
            this->p[i].second = i+1;
        }
        this->p[MAX_SIZE-1].second = 0;
    }
}

template<class TheClass>
TheClass StaticList<TheClass>::getVal(const U_L_L &index) const {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index>=this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }
    U_L_L currentIndex = this->p[MAX_SIZE-1].second;
    for(U_L_L i=0; i<index; ++i) {
        currentIndex = this->p[currentIndex].second;
    }
    return this->p[currentIndex].first;
}

template<class TheClass>
U_L_L StaticList<TheClass>::findVal(const TheClass &val) const {
    if(this->isEmpty()) {
        EXCEPTION_IS_EMPTY;
    }
    U_L_L currentIndex = this->p[MAX_SIZE-1].second;
    while(0 != currentIndex) {
        if(val == this->p[currentIndex].first) {
            return currentIndex;
        }
        currentIndex = this->p[currentIndex].second;
    }
    throw EXCEPTION_CAN_NOT_FIND;
}

template<class TheClass>
void StaticList<TheClass>::insertVal(const TheClass &val, const U_L_L &index) {
    if(index > this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    this->size++;

    U_L_L newIndex = this->p[0].second;
    this->p[0].second = this->p[newIndex].second;
    this->p[newIndex].first = val;

    U_L_L currentIndex = this->p[MAX_SIZE-1].second;
    if(0 == index) {//头
        this->p[newIndex].second = currentIndex;
        this->p[MAX_SIZE-1].second = newIndex;
    }
    else if(this->size-1 == index) {//尾
        while(0 != this->p[currentIndex].second) {
            currentIndex = this->p[currentIndex].second;
        }
        this->p[newIndex].second = 0;
        this->p[currentIndex].second = newIndex;
    }
    else {
        //定位到目标位置前一个节点
        for(U_L_L i=1; i<index; ++i) {
            currentIndex = this->p[currentIndex].second;
        }
        this->p[newIndex].second = this->p[currentIndex].second;
        this->p[currentIndex].second = newIndex;
    }
}

template<class TheClass>
TheClass StaticList<TheClass>::deleteWithIndex(const U_L_L &index) {
    if(this->isEmpty()) {
        throw EXCEPTION_IS_EMPTY;
    }
    if(index >= this->size) {
        throw EXCEPTION_OUT_OF_BOUNDS;
    }

    this->size--;

    U_L_L deleteIndex;
    U_L_L currentIndex = this->p[MAX_SIZE-1].second;
    if(0 == index) {//头
        deleteIndex = currentIndex;
        this->p[MAX_SIZE-1].second = this->p[currentIndex].second;
        this->p[currentIndex].second = this->p[0].second;
        this->p[0].second = currentIndex;
    }
    else if(this->size == index) {//尾
        //定位到倒数第二个节点，即删除目标元素后的链表中最后一个节点
        for(U_L_L i=1; i<this->size; ++i) {
            currentIndex = this->p[currentIndex].second;
        }
        deleteIndex = this->p[currentIndex].second;
        this->p[deleteIndex].second = this->p[0].second;
        this->p[0].second = deleteIndex;
        this->p[currentIndex].second = 0;
    }
    else {
        //定位到目标位置前一个节点
        for(U_L_L i=1; i<index; ++i) {
            currentIndex = this->p[currentIndex].second;
        }
        deleteIndex = this->p[currentIndex].second;
        this->p[currentIndex].second = this->p[deleteIndex].second;
        this->p[deleteIndex].second = this->p[0].second;
        this->p[0].second = deleteIndex;
    }
    return this->p[deleteIndex].first;
}

template<class TheClass>
void StaticList<TheClass>::print(void) {
    cout << "打印静态链表：[ ";
    U_L_L currentIndex = this->p[MAX_SIZE-1].second;
    while(0 != currentIndex) {
        cout << this->p[currentIndex].first << ' ';
        currentIndex = this->p[currentIndex].second;
    }
    cout << ']' << endl;
}

}

#endif